﻿#include <stdio.h>

void swap(int *a, int *b);

void printArray(int arr[], int size);

void quickSort(int arr[], int left, int right);

void dualPivotQuickSort(int arr[], int start, int end);

void merge(int arr[], int left, int mid, int right);

void mergeSort(int arr[], int left, int right);

//希尔排序
void shellSort(int arr[], int size);

void shellSort2(int arr[], int size){
    int delta = size / 2;
    while (delta >= 1) {
        //这里依然是使用之前的插入排序，不过此时需要考虑分组了
        for (int i = delta; i < size; ++i) {   //我们需要从delta开始，因为前delta个组的第一个元素默认是有序状态
            int j = i, tmp = arr[i];   //这里依然是把待插入的先抽出来
            while (j >= delta && arr[j - delta] > tmp) {
                //注意这里比较需要按步长往回走，所以说是j - delta，此时j必须大于等于delta才可以，如果j - delta小于0说明前面没有元素了
                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = tmp;
        }
        delta /= 2;    //分组插排完事之后，重新计算步长
    }
}

int main() {
    int test[10] = {9, 6, 5, 5, 3, 2, 1, 0, 7, 8};
    printArray(test, 10);
    shellSort(test, 10);
    printArray(test, 10);
    return 0;
}

void shellSort(int arr[], int size) {
    int gap, i, j, temp;
    for (gap = size / 2; gap > 0; gap /= 2) {
        for (i = gap; i < size; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    int i, j, k;
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}


void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int l = left, r = right;
    int base = arr[left];
    while (l < r) {
        while (l < r && arr[r] >= base) --r;
        while (l < r && arr[l] <= base) ++l;
        swap(&arr[l], &arr[r]);
    }
    arr[left] = arr[l];
    arr[l] = base;
    quickSort(arr, left, l - 1);
    quickSort(arr, l + 1, right);
}

void dualPivotQuickSort(int arr[], int start, int end) {
    if (start >= end) return;     //首先结束条件还是跟之前快速排序一样，因为不可能无限制地分下去，分到只剩一个或零个元素时该停止了
    if (arr[start] > arr[end])    //先把首尾两个基准进行比较，看看谁更大
        swap(&arr[start], &arr[end]);    //把大的换到后面去
    int pivot1 = arr[start], pivot2 = arr[end];    //取出两个基准元素
    int left = start, right = end, mid = left + 1;   //因为分了三块区域，此时需要三个指针来存放
    while (mid < right) {    //因为左边冲在最前面的是mid指针，所以说跟之前一样，只要小于right说明mid到right之间还有没排序的元素
        if (arr[mid] < pivot1)     //如果mid所指向的元素小于基准1，说明需要放到最左边
            swap(&arr[++left], &arr[mid++]);   //直接跟最左边交换，然后left和mid都向前移动
        else if (arr[mid] <= pivot2) {    //在如果不小于基准1但是小于基准2，说明在中间
            mid++;   //因为mid本身就是在中间的，所以说只需要向前缩小范围就行
        } else {    //最后就是在右边的情况了
            while (arr[--right] > pivot2 && right > mid);  //此时我们需要找一个右边的位置来存放需要换过来的元素，注意先移动右边指针
            if (mid >= right) break;   //要是把剩余元素找完了都还没找到一个比基准2小的，那么就直接结束，本轮排序已经完成了
            swap(&arr[mid], &arr[right]);   //如果还有剩余元素，说明找到了，直接交换right指针和mid指针所指元素
        }
    }
    swap(&arr[start], &arr[left]);    //最后基准1跟left交换位置，正好左边的全部比基准1小
    swap(&arr[end], &arr[right]);     //最后基准2跟right交换位置，正好右边的全部比基准2大
    dualPivotQuickSort(arr, start, left - 1);    //继续对三个区域再次进行双轴快速排序
    dualPivotQuickSort(arr, left + 1, right - 1);
    dualPivotQuickSort(arr, right + 1, end);
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    putchar('\n');
}

